home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 13429 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.0 KB
  1. Path: mail2news.demon.co.uk!genesis.demon.co.uk
  2. From: Lawrence Kirby <fred@genesis.demon.co.uk>
  3. Newsgroups: comp.lang.c
  4. Subject: Re: fast find algorithm
  5. Date: Sat, 06 Apr 96 21:05:54 GMT
  6. Organization: none
  7. Message-ID: <828824754snz@genesis.demon.co.uk>
  8. References: <Dp8wE6.8DG@cix.compulink.co.uk> <4ju12t$ovh@news.xs4all.nl>
  9. Reply-To: fred@genesis.demon.co.uk
  10. X-NNTP-Posting-Host: genesis.demon.co.uk
  11. X-Newsreader: Demon Internet Simple News v1.27
  12. X-Mail2News-Path: genesis.demon.co.uk
  13.  
  14. In article <4ju12t$ovh@news.xs4all.nl> falstaff@xs4all.nl "Falstaff" writes:
  15.  
  16. >setheridge@cix.compulink.co.uk ("Stephen Etheridge") writes:
  17. >
  18. >>Hi
  19. >
  20. >>Does anyone have an search algoritm faster than a binary chop for the 
  21. >>following:
  22. >
  23. >>find a date from a sorted array of 1500 possible storage locations
  24. >
  25. >It is theoretically not possible to find an entry in a sorted list
  26. >in less than ceil(2log(N)) (=11 in this case) operations.  bsearch()
  27. >does just that, so if it isn't fast enough you should try other methods.
  28.  
  29. That may be true for the worst case but you can do better on average
  30. if you know something about the distribution of values. An example
  31. has been posted.
  32.  
  33. >A plain table lookup is fastest, but can only be done if the number
  34. >of elements isn't too great
  35.  
  36. I think you mean the number of possible values of the key.
  37.  
  38. >-- would not work for dates unless you
  39. >aren't interested in the year part, or if you have tons of memory
  40. >(need 31*12*100 elements if you ignore the century).
  41. >
  42. >Hashing is slightly slower than straight table lookup and can't be
  43. >used when you want to delete elements from your table.
  44.  
  45. It can, you can use a technique like deleted item markers.
  46.  
  47. >If you want to minimize time to *successfully* searching elements,
  48. >and a few elements account for>90% of your input, you can sort the
  49. >array into order of searches and use a linear search.
  50.  
  51. That leaves you vulnerable to unpleasant worst case behaviour.
  52.  
  53. -- 
  54. -----------------------------------------
  55. Lawrence Kirby | fred@genesis.demon.co.uk
  56. Wilts, England | 70734.126@compuserve.com
  57. -----------------------------------------
  58.